package com.learn.algorlthm;

/**
 * @classname:
 * @Description:二叉搜索树与双向链表
 * @author: yfpu(fengpu.yang @ ucarinc.com)
 * @Date: 2018-08-04 11:29
 * 题目描述：
 * 输入一棵二叉搜索树，将该二叉搜索树转换成一个排序的双向链表。要求不能创建任何新的结点，只能调整树中结点指针的指
 * 向。
 */
public class Learn36 {

    private static TreeNode pre = null;
    private static TreeNode head = null;


    public static TreeNode convert(TreeNode treeNode) {
        inOrder(treeNode);
        return head;
    }

    private static void inOrder(TreeNode treeNode) {
        if (treeNode == null)
            return;
        inOrder(treeNode.left);

        treeNode.left = pre;
        if (pre != null)
            pre.right = treeNode;
        pre = treeNode;
        if (head == null)
            head = treeNode;

        inOrder(treeNode.right);


    }



    static class TreeNode{
        public int value;

        public TreeNode left;
        public TreeNode right;

        public TreeNode() {
        }

        public TreeNode(int value) {
            this.value = value;
        }
    }

}
